// 如何判断分治问题
// 1.问题可以被分解
// 2.子问题是独立的
// 3.子问题的解可以被合并
/**
 * 分治常见应用: 寻找最近点对, 大整数乘法, 矩阵乘法, 汉诺塔问题. 求解逆序对
 * */

/**
 * @author hyun
 * @date 2024/03/29
 * @param nums
 * @param left
 * @param mid
 * @param right
 * @returns {any[]}
 */
function merge(nums, left, mid, right) {
    // 左子数组区间[left, mid], 右子数组区间[mid+1, right]
    // 存放合并后的结果
    const tmp = new Array(right - left + 1)
    // 初始化左子数组和右子数组的起始数组
    let i = left, j = mid + 1, k = 0
    // 当左右数组都还有元素时, 比较并将较小的元素赋值到临时数组中
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++]
        } else {
            tmp[k++] = nums[j++]
        }
    }
    while (i <= mid) {
        tmp[k++] = nums[i++]
    }
    while (j <= right) {
        tmp[k++] = nums[j++]
    }
    for (k = 0; k < tmp.length; k++) {
        nums[left + k] = tmp[k]
    }
    return tmp
}

function mergeSort(nums, left, right) {
    // 递归终止条件
    if (left >= right) return
    // 划分阶段
    let mid = left + ((right - left) >> 1)
    mergeSort(nums, left, mid)
    mergeSort(nums, mid + 1, right)
    // 合并
    return merge(nums, left, mid, right)
}

console.log("mergeSort: ", mergeSort([21, 12, 3, 85, 233, 65], 0, [21, 12, 3, 85, 233, 65].length - 1))


/**
 * 二分搜索
 * @author hyun
 * @date 2024/03/29
 * @param nums
 * @param target
 * @param i
 * @param j
 * @desc >> 右操作符(操作的不是十进制本身, 而是十进制所对应的二进制数) 5 -> 0101
 * @returns {null|*}
 */
function dfs(nums, target, i, j) {
    if (i > j) return null
    let mid = i + ((j - i) >> 1)
    if (nums[mid] < target) {
        // 目标值在右边`
        return dfs(nums, target, mid + 1, j)
    } else if (nums[mid] > target) {
        // 目标值在左边
        return dfs(nums, target, i, mid - 1)
    } else {
        // 找到目标元素
        return mid
    }
}

let arr = [1, 12, 33, 34, 65, 68]
let rst1 = dfs(arr, 4, 0, arr.length - 1)
console.log(rst1)
let rst2 = dfs(arr, 12, 0, arr.length - 1)
console.log(rst2)


// 构建二叉树问题
/** 给定一个二叉树的前序遍历preorder和中序遍历inorder 请从中构建二叉树, 返回二叉树的根节点 */
// preorder: 39217 inorder: 93127
class TreeNode {
    constructor(key, left = null, right = null) {
        this.key = key
        this.left = left
        this.right = right
    }
}

const dfsDivide = function (preorder, inorederMap, i, l, r) {
    if (r - l < 0) return null
    // 初始化根节点
    const root = new TreeNode(preorder[i])
    // 查询m
    const m = inorederMap.get(preorder[i])
    // 子问题: 构建左子树
    root.left = dfsDivide(preorder, inorederMap, i + 1, l, m - 1)
    root.right = dfsDivide(preorder, inorederMap, i + 1 + m - l, m + 1, r)
    return root
}


/**
 * @author hyun
 * @date 2024/03/30
 * @param preorder 二叉树的前序遍历
 * @param inorder 二叉树的中序遍历
 * @returns {TreeNode}
 */
function buildTree(preorder, inorder) {
    let inoderMap = new Map()
    for (let i = 0, len = inorder.length; i < len; i++) {
        inoderMap.set(inorder[i], i)
    }
    const root = dfsDivide(preorder, inoderMap, 0, 0, inorder.length - 1)
    return root
}

console.log("buildTree: ", buildTree([3, 9, 2, 1, 7], [9, 3, 1, 2, 7]))

function preOrder(root, res) {
    if (root == null) return
    if (root.key === 7) {
        res.push(root)
    }
    preOrder(root.left, res)
    preOrder(root.right, res)
    return res
}

console.log("preOrder:", preOrder(buildTree([3, 9, 2, 1, 7], [9, 3, 1, 2, 7]), []))


// 回溯算法: 从一个初始状态出发, 暴力搜索所有可能的解决方案, 当遇到正确的解 将其记录, 知道找到解或者尝试了所有可能的选择 都无法找到解为止
// 在二叉树中搜索所有值为7的节点,请返回根节点到这些节点的路径
/**
 * @author hyun
 * @date 2024/03/31
 * @param root
 * @param path  记录访问过的节点路径
 * @param res 结果列表
 * @private
 */
function _preOrder(root, path, res) {
    if (root === null) return
    path.push(root)
    if (root.key == 7) {
        // 记录解
        res.push([...path])
    }
    _preOrder(root.left, path, res)
    _preOrder(root.right, path, res)
    // 回退
    path.pop()
    return res
}

const _root = {
    key: 1,
    left: {key: 7, left: {key: 4, left: null, right: null}, right: {key: 5, left: null, right: null}},
    right: {
        key: 3,
        left: {key: 6, left: null, right: null},
        right: {key: 7, left: null, right: null}
    }
}
console.log("_preOrder: ", _preOrder(_root, [], []))


// 剪枝, 在二叉树中搜索所有值为7的节点, 请返回根节点到这些节点的路径 并要求路径中不含3的节点
function __preOrder(root, path, res) {
    if (root === null || root.key == 3) return
    path.push(root)
    if (root.key == 7) {
        res.push([...path])
    }
    __preOrder(root.left, path, res)
    __preOrder(root.right, path, res)
    path.pop()
    return res
}

console.log("__preOrder: ", __preOrder(_root, [], []))

/**
 * 回溯算法框架
 * @author hyun
 * @date 2024/04/02
 * @param state 表示问题的当前状态
 * @param choices 当前状态下可以做出的选择
 * @param res
 */
function backtrack(state, choices, res) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
    }
    // 遍历所有的选择
    for (const choiceKey of Object.keys(choices)) {
        const choice = choices[choiceKey];
        // 剪枝: 判断选择是否合法
        if (isValid(choice)) {
            // 尝试: 做出选择, 更新状态
            makeChoice(state, choice);
            backtrack(state, choice, res);
            // 回退: 撤销选择, 回复到之前的状态
            undoChoice(state);
        }
    }
    return res;
}

function isSolution(state) {
    return state && state[state.length - 1]?.key === 7;
}

// 记录结果
function recordSolution(state, res) {
    res.push([...state]);
}

// 判断选择是否合法
function isValid(choice) {
    return choice && choice.key !== 3;
}

// 更新状态
function makeChoice(state, choice) {
    state.push(choice);
}

// 恢复状态
function undoChoice(state) {
    state.pop();
}

// 初始化状态和调用回溯算法
const initialState = [_root];
const result = backtrack(initialState, _root, []);
console.log("backtrack: ", result);  // 输出结果

/* 全排列问题 */
// 在给定一个集合(如一个数组或字符串)的情况下, 找出这个集合中元素的所有可能的排列
// 输入 [1]    输出:[1]
// 输入 [1,2]  输出: [1,2] [2,1]
// 输入 [1,2,3] 输出: [1,2,3], [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

/**
 * @author hyun
 * @param state 问题的当前状态
 * @param choice 当前状态下可以做出的选择
 * @param selected 表示是否已经被选择
 * @param res
 */
function backtrackAll(state, choice, selected, res) {
    // 判断是否为解,(状态长度等于元素数量时)
    if (state.length == choice.length) {
        // 记录解
        res.push([...state])
        return
    }
    // 遍历所有选择
    for (let i = 0; i < choice.length; i++) {
        // 剪枝, 判断选择是否合法
        if (!selected[i]) {
            // 尝试, 做出选择
            selected[i] = true
            state.push(choice[i])
            // 进行下一轮选择
            backtrackAll(state, choice, selected, res)
            // 回退
            selected[i] = false
            state.pop()
        }
    }
    return res
}

const selected = new Array(3).fill(false)
console.log(backtrackAll([], [1, 2, 3], selected, []))


/**
 * @author hyun
 * @param state
 * @param choices
 * @param res
 * @param target 目标值
 * @private
 */
function _backtrackAll(state, choices, res, target, total) {
    if (total == target) {
        // 记录结果
        res.push([...state])
        return
    }
    // 遍历所有选择
    for (let i = 0, len = choices.length; i < len; i++) {
        if (total + choices[i] > target) {
            continue
        }
        // 尝试做出选择
        state.push(choices[i])
        // 进行下一轮选择
        _backtrackAll(state, choices, res, target, total + choices[i])
        // 回退, 撤销选择, 恢复到之前的状态
        state.pop()
    }
    return res
}

// 数组需排序
// function _backtrackAll(state, choices, res, target, start) {
//     if (target == 0) {
//         // 记录结果
//         res.push([...state])
//         return
//     }
//     // 遍历所有选择
//     for (let i = start, len = choices.length; i < len; i++) {
//         if (target - choices[i] < 0) {
//             break
//         }
//         // 尝试做出选择
//         state.push(choices[i])
//         // 进行下一轮选择
//         _backtrackAll(state, choices, res, target - choices[i], i)
//         // 回退, 撤销选择, 恢复到之前的状态
//         state.pop()
//     }
//     return res
// }

console.log(_backtrackAll([], [3, 4, 5], [], 9, 0))


// leetcode 17: 电话号码的字母组合
// 给定一个仅包含数组2-9的字符串, 返回所有他能表示的字母组合, 答案可以按任何顺序返回
// 输入: digit = '23'
// 输出: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
// 输入: ''
// 输出: []
// 0 <= digits.length <= 4
/**
 * @param {string} digits
 * @return {string[]}
 */

var letterCombinations = function (digits) {
    let enumNum = {
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z'],
    }
    // 边界值处理
    if (digits.length == 0) return []
    // 如果数字长度为1, 说明电话号码只有一位
    if (digits.length == 1) return enumNum[digits]
    const rst = []

    function backtrack(state, nextDigits) {
        if (nextDigits.length == 0) {
            //  记录结果
            rst.push(state)
        } else {
            // 获取当前数字对应的字母集合
            const curDigits = nextDigits[0]
            const letters = enumNum[curDigits]
            // 遍历所有的可能结果
            for (let i = 0; i < letters.length; i++) {
                const letter = letters[i]
                backtrack(state + letter, nextDigits.substring(1))
            }
        }
    }

    backtrack('', digits)
    return rst
};
console.log(letterCombinations('2'))
console.log(letterCombinations('23'))


/**
 * @author hyun
 * @param {number[]} nums
 * @return {number[][]}
 * @date 20240402
 * 给定一个包含重复数字的序列nums 按任意顺序返回所有不重复的全排列
 */
var permuteUnique = function (nums) {
    if (nums.length == 0) return []
    let res = []
    let selected = new Array(nums.length).fill(false)
    nums = nums.sort((a, b) => a - b)
    backtrack(0, [], nums)

    function backtrack(idx, state, choices) {
        if (idx == choices.length) {
            res.push([...state])
        }
        for (let i = 0; i < choices.length; ++i) {
            // 剪枝
            if (selected[i] || (i > 0 && choices[i] === choices[i - 1] && !selected[i - 1])) {
                continue
            }
            // 尝试做出选择
            state.push(choices[i])
            selected[i] = true
            // 进行下一轮选择
            backtrack(idx + 1, state, choices)
            // 回退
            selected[i] = false
            state.pop()
        }
    }

    return res
};
console.log(permuteUnique([1, 1, 2]))


/**
 * 数字n 代表生成括号的对数, 请你设计一个函数, 用于能够生成所有可能的并且有效的括号组合
 *  生成左枝叶的条件时: 左括号剩余数量(严格) 大于 0
 *  可以生成右枝叶的条件 左括号剩余数量 小于右括号剩余数量
 * @author hyun
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    let res = []
    backtrack('', n, n, res)

    function backtrack(curStr, left, right, res) {
        if (left == 0 && right == 0) {
            res.push(curStr)
            return
        }
        if (left > right) return
        // 遍历所有选择
        if (left > 0) {
            backtrack(curStr + '(', left - 1, right, res)
        }
        if (right > 0) {
            backtrack(curStr + ')', left, right - 1, res)
        }
    }

    return res
    // function backtrack(state, choices, res) {
    //     // 判断是否为解
    //     if (isSolution(state)) {
    //         // 记录解
    //         recordSolution(state, res)
    //         // 停止继续搜索
    //         return
    //     }
    //     // 遍历所有选择
    //     for (let i = 0; i < choices.length; i++) {
    //         // 剪枝 判断选择是否合法
    //         if(isValid(state, choices)) {
    //             // 尝试做出选择, 更新状态
    //             // 开启下一轮循环
    //             // 回退; 撤销选择, 恢复到之前状态
    //         }
    //     }
    // }
};
console.log(generateParenthesis(3))


// N 皇后问题: 根据国际象棋的规则, 皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子
// 给定n 个皇后和一个n*n大小的棋盘, 寻找使得所有皇后之间无法相互攻击的摆放方案
/**
 * @author hyun
 * @date 2024/04/03
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
    const state = Array.from({length: n}, () => Array(n).fill('#'))
    const cols = Array(n).fill(false)
    const diags1 = Array(2 * n - 1).fill(false)
    const diags2 = Array(2 * n - 1).fill(false)
    const res = []
    backtrack(0, n, state, res, cols, diags1, diags2)
    return res

    /**
     * @param row 行
     * @param n 方格
     * @param state 当前状态下能做出的选择
     * @param res 结果
     * @param cols 列
     * @param diags1 主对角线
     * @param diags2 次对角线
     */
    function backtrack(row, n, state, res, cols, diags1, diags2) {
        console.log(diags2)
        // 放置所有行记录解
        if (row === n) {
            res.push(state.map(row => row.slice()))
            return
        }
        // 遍历所有的选择
        for (let col = 0; col < n; col++) {
            // 计算该格子对应的主对角线
            const diag1 = row - col + n - 1
            const diag2 = row + col
            // 剪枝 不允许该格子所在行, 列 主对角线 副对角线存在皇后
            if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
                // 尝试做出选择
                state[row][col] = 'Q'
                cols[col] = diags1[diag1] = diags2[diag2] = true
                // 进行下一轮选择
                backtrack(row + 1, n, state, res, cols, diags1, diags2)
                // 回退
                state[row][col] = '#'
                cols[col] = diags1[diag1] = diags2[diag2] = false
            }
        }
    }
};
console.log("solveNQueens: ", solveNQueens(4))


// 子集 给你一个整数数组nums 数组中的元素互不相同, 返回该数组所有可能的子集, 解集 不能包含重复的子集
// 输入 nums=[1,2,3]
// 输出 [[], [1], [2], [3], [1,2], [1,3], [1, 2,3], [2,3]]
// 输入 nums= [0]
// 输出 [[], [0]]
var subsets = function (nums) {
    let rst = []
    const selected = new Array(3).fill(false)
    backtrack(0, [], nums, rst)
    return rst

    function backtrack(idx, state, choices, rst) {
        // 什么时候记录解?
        rst.push([...state])
        // 遍历所有的选择
        for (let i = idx; i < choices.length; i++) {
            if (!selected[i]) {
                // 尝试做出选择
                state.push(choices[i])
                selected[i] = true
                backtrack(i + 1, state, choices, rst)
                // 回退
                selected[i] = false
                state.pop()
            }

        }
    }
};
console.log(subsets([1, 2, 3]))


/**
 * @author hyun
 * @date 2024/04/03
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
    let rst = []
    nums = nums.sort((a, b) => a - b)
    const selected = new Array(3).fill(false)
    backtrack(0, [], nums, rst)

    function backtrack(start, state, choices, rst) {
        // 记录解
        rst.push([...state])
        for (let i = start; i < choices.length; i++) {
            // 数组需排序 进行剪枝
            if (selected[i] || (i > 0 && choices[i] === choices[i - 1] && !selected[i - 1])) {
                continue
            }
            // 尝试做选择
            selected[i] = true
            state.push(choices[i])
            // 开启下一轮循环
            backtrack(i + 1, state, choices, rst)
            // 回退


            selected[i] = false
            state.pop()
        }
    }

    return rst
};
console.log("subsetsWithDup: ", subsetsWithDup([1, 2, 2]))


/** dynamic programming 动态规划, 他将一个问题分解为一系列更小的子问题, 并通过存储于子问题的解来避免重复计算 */

/* quetion1 爬楼梯: 给定一个共有n阶的楼梯, 你每步可以向上1阶或者2阶, 请问有多少种方案 */

function climbingStairsBacktrack(n) {
    const choices = [1, 2]
    const state = 0
    const res = new Map()
    res.set(0, 0)
    backtrack(state, choices, n, res)
    return res.get(0)

    function backtrack(state, choices, n, res) {
        if (state == n) {
            // 记录解
            res.set(0, res.get(0) + 1)
        }
        for (const choice of choices) {
            if (choice + state > n) {
                break
            }
            backtrack(state + choice, choices, n, res)
        }
    }
}

console.log("climbingStairsBacktrack: ", climbingStairsBacktrack(3))


/**
 * @author hyun
 * @date 2024/04/03
 * @param n
 * @returns {*[]}
 * @description 与上述方法不同, 此方法会返回具体的解
 * @private
 */
function _climbingStairsBacktrack(n) {
    const choices = [1, 2]
    const state = 0
    const res = []
    backtrack(state, choices, n, [], res)
    return res

    function backtrack(state, choices, n, path, res) {
        if (state === n) {
            res.push([...path])
            return
        }
        for (const choice of choices) {
            if (choice + state > n) {
                break
            }
            path.push(choice)
            backtrack(state + choice, choices, n, path, res)
            path.pop()
        }
    }
}

console.log(_climbingStairsBacktrack(3))

/**
 * 暴力搜索
 * @param n
 * @returns {*}
 * @private
 */
function __climbingStairsBacktrack(n) {
    return dfs(n)

    function dfs(i) {
        if (i == 1 || i == 2) return i
        return dfs(i - 1) + dfs(i - 2)
    }
}

console.log(__climbingStairsBacktrack(5))


/**
 * 记忆化搜索, 从顶至底, 优化暴力搜索法中 dp子问题重复计算问题 dp[9] -> dp[8] + dp[7]; dp[8] -> dp[7] + dp[6]
 * @param n
 * @returns {*}
 * @private
 * @description: 数组mem, 初始化长度n+1,当楼梯书为0时,即n为0时此时有一种解法(不爬), 故应初始化dp数组长度为n+1
 */
function ___climbingStairsBacktrack(n) {
    return dfs(n, new Array(n + 1).fill(-1))

    function dfs(i, mem) {
        if (i == 1 || i == 2) return i
        if (mem[i] != -1) {
            return mem[i]
        }
        const count = dfs(i - 1, mem) + dfs(i - 2, mem)
        mem[i] = count
        return count
    }
}

console.log("___climbingStairsBacktrack: ", ___climbingStairsBacktrack(5))


// 动态规划: [dp 表], dp[i] 表示状态i对应子问题的解, 初始状态: 最小问题对应的状态, 状态转移方程: dp[n] = dp[n-1] + dp[n-2]
/**
 * 动态规划法
 * @param n
 * @returns {any}
 * @private
 */
function __climbingStairsDP(n) {
    if (n == 1 || n == 2) return n
    // 初始化dp表, 用于存储子问题的解
    const dp = new Array(n + 1).fill(-1)
    // 预设最小子问题的解
    dp[1] = 1
    dp[2] = 2
    // 状态转移, 状态转移方程 dp[n] = dp[n-1] + dp[n-2]
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[i]
}


// 最小路径和
// 给定一个n xm 的二维网格 grid，网格中的每个单元格包含一个非负整数，表示该单元格的代价。机器人以左上角单元格为起始点，
// 每次只能向下或者向右移动一步，直至到达右下角单元格。请返回从左上角到右下角的最小路径和。
/*
* step:
*   思考每轮的决策,定义状态, 从而得到dp表
*   找出最优子结构, 进而推导出状态转移方程
*   确定边界条件和状态转移顺序
* */
function minPathSumDFS(grid, i, j) {
    // 若为左上角单元格, 则终止搜索
    if (i === 0 && j === 0) {
        return grid[0][0]
    }
    // 若行列索引越界
    if (i < 0 || j < 0) {
        return Infinity
    }
    const up = minPathSumDFS(grid, i - 1, j)
    const left = minPathSumDFS(grid, i, j - 1)
    // 返回左上角到(i, j)的最小路径代价
    // 最优子结构为: 到达[i,j]的最小路径和由[i, j-1]的最小路径和与[i-1, j]的最小路径和, 这两者较小的哪一个决定
    return Math.min(left, up) + grid[i][j]
}

const grid = [[1, 2, 5, 4], [3, 2, 3, 3], [1, 4, 2, 5], [5, 2, 1, 2]]
console.log("minPathSumDFS: ", minPathSumDFS(grid, 3, 3))


/* 最小路径和: 记忆化搜索*/
function minPathSumDFSMem(grid, mem, i, j) {
    // 若为左上角单元格,则终止搜索
    if (i === 0 && j === 0) {
        return grid[0][0]
    }
    if (i < 0 || j < 0) {
        return Infinity
    }
    if (mem[i][j] !== -1) {
        return mem[i][j]
    }
    const up = minPathSumDFSMem(grid, mem, i - 1, j)
    const left = minPathSumDFSMem(grid, mem, i, j - 1)
    mem[i][j] = Math.min(left, up) + grid[i][j]
    return mem[i][j]
}

const rows = grid.length;
const cols = grid[0].length;
const mem = Array.from({length: rows}, () => Array(cols).fill(-1))
console.log("minPathSumDFSMem: ", minPathSumDFSMem(grid, mem, 3, 3))


function minPathSumDP(grid) {
    const n = grid.length,
        m = grid[0].length
    // 初始化dp表
    const dp = Array.from({length: n}, () =>
        Array.from({length: m}, () => 0)
    )
    dp[0][0] = grid[0][0]
    // 状态转移: 首行
    for (let j = 1; j < m; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    }
    // 状态转移: 首列
    for (let i = 1; i < n; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    }
    // 状态转移: 其他行列
    for (let i = 1; i < n; i++) {
        for (let j = 1; j < m; j++) {
            dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
        }
    }
    return dp[n - 1][m - 1]
}

console.log("minPathSumDP: ", minPathSumDP(grid))


// 0-1 背包问题
// 给定n个物品，第i个物品的重量为 wgt[i- 1]、价值为 ual[i-1]，和一个容量为 cap 的背包。
// 每个物品只能选择一次，问在不超过背包容量下能放入物品的最大价值。
/**
 * @author hyun
 * @param wgt 物品重量
 * @param val 价值
 * @param i 当前要考虑物品的索引
 * @param c 当前背包的剩余容量
 * @returns {number|number|*|number}
 */
function knapsackDFS(wgt, val, i, c) {
    // 若已经选完所有物品或背包无容量
    if (i === 0 || c === 0) {
        return 0
    }
    // 若超过背包容量,则只能不放入背包
    if (wgt[i - 1] > c) {
        return knapsackDFS(wgt, val, i - 1, c)
    }
    // 计算不放入和放入物品i的最大价值
    const no = knapsackDFS(wgt, val, i - 1, c)
    const yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1]
    return Math.max(no, yes)
}

const wgt = [10, 20, 30]
const val = [60, 110, 120]
console.log("knapsackDFS: ", knapsackDFS(wgt, val, wgt.length, 50))

/**
 * @author hyun
 * @date 2024/04/9
 * @param wgt
 * @param val
 * @param mem
 * @param i
 * @param c
 * @returns {number|*|number}
 */
function knapsackDFSMem(wgt, val, mem, i, c) {
    if (i === 0 || c === 0) return 0
    if (mem[i][c] !== -1) {
        return mem[i][c]
    }
    if (wgt[i - 1] > c) return knapsackDFSMem(wgt, val, mem, i - 1, c)
    const no = knapsackDFSMem(wgt, val, mem, i - 1, c)
    const yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1]
    mem[i][c] = Math.max(no, yes)
    return mem[i][c]
}

const _mem = Array.from({length: wgt.length + 1}, () => Array(51).fill(-1))
console.log("knapsackDFSMem: ", knapsackDFSMem(wgt, val, _mem, wgt.length, 50))
// n轮决策组成的过程, 每个物体都有放入和不放入两种决策
// 思考每轮的决策,定义状态, 从而得到dp表
// 找出最优子结构 进入推导出状态转移方程

function knapsackDP(wgt, val, cap) {
    const n = wgt.length
    // 初始化dp表
    const dp = Array(n + 1).fill(0).map(() => Array(cap + 1).fill(0))
    for (let i = 1; i <= n; i++) {
        for (let c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 如果当前物品的重量大于c, 不选
                dp[i][c] = dp[i - 1][c]
            } else {
                // 不选和选物品i 这两种方案的较大值
                dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1])
            }
        }
    }
    return dp[n][cap]
}

const _wgt = [1, 2, 3]
const _val = [5, 11, 15]
console.log("knapsackDP: ", knapsackDP(_wgt, _val, 4))

/**
 * 如果采取正序遍历, 那么遍历到dp[i,j]时, 左上方dp[i-1, 1] ~ dp[i-1,j-1]值可能被覆盖, 此时采取倒叙的方式 就不会发生覆盖问题
 * @param wgt
 * @param val
 * @param cap
 */
function knapsackDPComp(wgt, val, cap) {
    const n = wgt.length
    const dp = Array(cap + 1).fill(0)
    // 状态转移
    for (let i = 1; i <= n; i++) {
        // 倒叙遍历
        for (let c = cap; c >= 1; c--) {
            if (wgt[i - 1] <= c) {
                // 不选和选物品i这两种方案的较大值
                dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
            }
        }
    }
    return dp[cap]
}

console.log("knapsackDPComp: ", knapsackDPComp(wgt, val, 50))
/* 完全背包问题 */
// 给定n个物品, 第i个物品的重量为wgt[i-1]、价值为val[i-1], 和一个容量为cap的背包 每个物品可以重复选取, 问不超过背包容量下能放入物品的最大价值
// (0-1背包问题) dp[i, c] = max(dp[i-1,c], dp[i-1, c-wgt[i-1]] + val[i-1])
/**
 * @author hyun
 * @date 2024/04/09
 * @param wgt
 * @param val
 * @param cap
 * @returns {number}
 */
function unboundedKnapsackDP(wgt, val, cap) {
    const n = wgt.length
    // 初始化dp表
    const dp = Array.from({length: n + 1}, () => Array.from({length: cap + 1}, () => 0))
    // 状态转移
    for (let i = 1; i <= n; i++) {
        for (let c = 1; c <= cap; c++) {
            if (wgt[i - 1] > c) {
                // 若超过背包容量,则不选物品i
                dp[i][c] = dp[i - 1][c]
            } else {
                // 不选物品和选物品i这两种方案的较大值
                dp[i][c] = Math.max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1])
            }
        }
    }
    return dp[n][cap]
}

console.log("unboundedKnapsackDP: ", unboundedKnapsackDP(wgt, val, 50))
/* 零钱兑换问题 */
// 给定n种硬币, 第i种硬币的面值为coins[i-1], 目标金额为amt, 每种硬币可以重复选取, 问能够凑出目标金额的最少硬币个数, 如果无法凑出目标金额则返回-1
// iList = [1,2,3], coins =  [1, 2, 5]

function coinChangeDP(coins, amt) {
    const n = coins.length
    const MAX = amt + 1
    // 初始化状态方程
    const dp = Array.from({length: n + 1}, () => Array.from({length: amt + 1}, () => 0))
    // 状态转移: 首行首列
    for (let a = 1; a <= amt; a++) {
        dp[0][a] = MAX
    }
    // 状态转移: 其余行列
    for (let i = 1; i <= n; i++) {
        for (let a = 1; a <= amt; a++) {

        }
    }
}
const yuan2fen = (val) => {
    val = val.toString()
    let i = val.indexOf('.')
    if (i === -1) {
        return val === '0' ? '0' : (val + '00')
    }
    return val.substring(0, i) + (val.substring(i + 1) + '000').substring(0, 2)
}

console.log('yuan2fen: ' +  yuan2fen(0.0286))